Search results for "Tabu search"
showing 10 items of 68 documents
Metaheuristic procedures for the lexicographic bottleneck assembly line balancing problem
2015
The goal of this work is to develop an improved procedure for the solution of the lexicographic bottleneck variant of the assembly line balancing problem (LB-ALBP). The objective of the LB-ALBP is to minimize the workload of the most heavily loaded workstation, followed by the workload of the second most heavily loaded workstation and so on. This problem-recently introduced to the literature (Pastor, 2011)-has practical relevance to manufacturing facilities. We design, implement and fine-tune GRASP, tabu search (TS) and scatter search (SS) heuristics for the LB-ALBP and show that our procedures are able to obtain solutions of a quality that outperforms previous approaches. We rely on both s…
GRASP and tabu search for the generalized dispersion problem
2021
Abstract The problem of maximizing dispersion requires the selection of a specific number of elements from a given set, in such a way that the minimum distance between the pairs of selected elements is maximized. In recent years, this problem has received a lot of attention and has been solved with many complex heuristics. However, there is a recent variant in which the selected elements have to satisfy two realistic constraints, a minimum capacity limit and a maximum budget, which in spite of its practical significance in facility location, has received little attention. In this paper, we first propose mathematical models to obtain the optimal solution of small- and medium-size instances, …
Tabu Search to Plan Schedules in a Multiskill Customer Contact Center
2006
International audience; We have studied a realistic case of scheduling problem in a customer contact center, dealing with multiskill agents. Our model combines the last two steps of the standard approach by determining shifts and by assigning them to agents at the same time (scheduling and rostering). Moreover, we have considered realistic vacations, according to legal constraints and preferences of agents. We have envisioned entire weeks of work, with variable meal times and meal durations, without overtime. In this paper, we define the problem and describe a Tabu search based solution.
Heuristics for the capacitated modular hub location problem
2017
Abstract In this paper we study the hub location problem, where the goal is to identify an optimal subset of facilities (hubs) to minimize the transportation cost while satisfying certain capacity constraints. In particular, we target the single assignment version, in which each node in the transportation network is assigned to only one hub to route its traffic. We consider here a realistic variant introduced previously, in which the capacity of edges between hubs is increased in a modular way. This reflects the practical situation in air traffic where the number of flights between two locations implies a capacity in terms of number of passengers. Then, the capacity can be increased in a mo…
Adaptive memory programing for the robust capacitated international sourcing problem
2008
The International Sourcing Problem consists of selecting a subset from an available set of potential suppliers internationally located. The selected suppliers must meet the demand for items from a set of plants, which are also located worldwide. Since the costs are affected by macroeconomic conditions in the countries where the supplier and the plant are located, the formulation considers the uncertainty associated with changes in these conditions. We formulate the robust capacitated international sourcing problem by means of a scenario-optimization approach. When dealing with uncertainty, one of the most common approaches in the literature is to formulate the problem via a set of possible …
Scatter Search and Path Relinking: Foundations and Advanced Designs
2004
Scatter Search and its generalized form Path Relinking, are evolutionary methods that have been successfully applied to hard optimization problems. Unlike genetic algorithms, they operate on a small set of solutions and employ diversification strategies of the form proposed in Tabu Search, which give precedence to strategic learning based on adaptive memory, with limited recourse to randomization. The fundamental concepts and principles were first proposed in the 1970s as an extension of formulations, dating back to the 1960s, for combining decision rules and problem constraints. (The constraint combination approaches, known as surrogate constraint methods, now independently provide an impo…
Heuristics and meta-heuristics for 2-layer straight line crossing minimization
2003
AbstractThis paper presents extensive computational experiments to compare 12 heuristics and 2 meta-heuristics for the problem of minimizing straight-line crossings in a 2-layer graph. These experiments show that the performance of the heuristics (largely based on simple ordering rules) drastically deteriorates as the graphs become sparser. A tabu search metaheuristic yields the best results for relatively dense graphs, with a GRASP implementation as close second. Furthermore, the GRASP approach outperforms all other approaches when tackling low-density graphs.
Tabu and Scatter Search for Artificial Neural Networks
2003
In this paper we address the problem of training multilayer feed-forward neural networks. These networks have been widely used for both prediction and classification in many different areas. Although the most popular method for training these networks is back propagation, other optimization methods such as tabu search or scatter search have been applied to solve this problem. This paper presents a new training algorithm based on the tabu search methodology that incorporates elements for search intensification and diversification by utilizing strategic designs where other previous approaches resort to randomization. Our method considers context and search information, as it is provided by th…
Neural network prediction in a system for optimizing simulations
2002
Neural networks have been widely used for both prediction and classification. Back-propagation is commonly used for training neural networks, although the limitations associated with this technique are well documented. Global search techniques such as simulated annealing, genetic algorithms and tabu search have also been used for this purpose. The developers of these training methods, however, have focused on accuracy rather than training speed in order to assess the merit of new proposals. While speed is not important in settings where training can be done off-line, the situation changes when the neural network must be trained and used on-line. This is the situation when a neural network i…
Tabu search for min-max edge crossing in graphs
2020
Abstract Graph drawing is a key issue in the field of data analysis, given the ever-growing amount of information available today that require the use of automatic tools to represent it. Graph Drawing Problems (GDP) are hard combinatorial problems whose applications have been widely relevant in fields such as social network analysis and project management. While classically in GDPs the main aesthetic concern is related to the minimization of the total sum of crossing in the graph (min-sum), in this paper we focus on a particular variant of the problem, the Min-Max GDP, consisting in the minimization of the maximum crossing among all egdes. Recently proposed in scientific literature, the Min…